home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / gxdda.h < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  5.6 KB  |  154 lines
  1. /* Copyright (C) 1994, 1995, 1996, 1997, 1998 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: gxdda.h,v 1.2 2000/09/19 19:00:35 lpd Exp $ */
  20. /* Definitions for DDAs */
  21. /* Requires gxfixed.h */
  22.  
  23. #ifndef gxdda_INCLUDED
  24. #  define gxdda_INCLUDED
  25.  
  26. /*
  27.  * We use the familiar Bresenham DDA algorithm for several purposes:
  28.  *      - tracking the edges when filling trapezoids;
  29.  *      - tracking the current pixel corner coordinates when rasterizing
  30.  *      skewed or rotated images;
  31.  *      - converting curves to sequences of lines (this is a 3rd-order
  32.  *      DDA, the others are 1st-order);
  33.  *      - perhaps someday for drawing single-pixel lines.
  34.  * In the case of trapezoids, lines, and curves, we need to use
  35.  * the DDA to find the integer X values at integer+0.5 values of Y;
  36.  * in the case of images, we use DDAs to compute the (fixed)
  37.  * X and Y values at (integer) source pixel corners.
  38.  *
  39.  * The purpose of the DDA is to compute the exact values Q(i) = floor(i*D/N)
  40.  * for increasing integers i, 0 <= i <= N.  D is considered to be an
  41.  * integer, although it may actually be a fixed.  For the algorithm,
  42.  * we maintain i*D/N as Q + (N-R)/N where Q and R are integers, 0 < R <= N,
  43.  * with the following auxiliary values:
  44.  *      dQ = floor(D/N)
  45.  *      dR = D mod N (0 <= dR < N)
  46.  *      NdR = N - dR
  47.  * Then at each iteration we do:
  48.  *      Q += dQ;
  49.  *      if ( R > dR ) R -= dR; else ++Q, R += NdR;
  50.  * These formulas work regardless of the sign of D, and never let R go
  51.  * out of range.
  52.  */
  53. /* In the following structure definitions, ntype must be an unsigned type. */
  54. #define dda_state_struct(sname, dtype, ntype)\
  55.   struct sname { dtype Q; ntype R; }
  56. #define dda_step_struct(sname, dtype, ntype)\
  57.   struct sname { dtype dQ; ntype dR, NdR; }
  58. /* DDA with fixed Q and (unsigned) integer N */
  59. typedef 
  60. dda_state_struct(_a, fixed, uint) gx_dda_state_fixed;
  61.      typedef dda_step_struct(_e, fixed, uint) gx_dda_step_fixed;
  62.      typedef struct gx_dda_fixed_s {
  63.      gx_dda_state_fixed state;
  64.      gx_dda_step_fixed step;
  65.      } gx_dda_fixed;
  66. /*
  67.  * Define a pair of DDAs for iterating along an arbitrary line.
  68.  */
  69.      typedef struct gx_dda_fixed_point_s {
  70.      gx_dda_fixed x, y;
  71.      } gx_dda_fixed_point;
  72. /*
  73.  * Initialize a DDA.  The sign test is needed only because C doesn't
  74.  * provide reliable definitions of / and % for integers (!!!).
  75.  */
  76. #define dda_init_state(dstate, init, N)\
  77.   (dstate).Q = (init), (dstate).R = (N)
  78. #define dda_init_step(dstep, D, N)\
  79.   if ( (N) == 0 )\
  80.     (dstep).dQ = 0, (dstep).dR = 0;\
  81.   else if ( (D) < 0 )\
  82.    { (dstep).dQ = -(-(D) / (N));\
  83.      if ( ((dstep).dR = -(D) % (N)) != 0 )\
  84.        --(dstep).dQ, (dstep).dR = (N) - (dstep).dR;\
  85.    }\
  86.   else\
  87.    { (dstep).dQ = (D) / (N); (dstep).dR = (D) % (N); }\
  88.   (dstep).NdR = (N) - (dstep).dR
  89. #define dda_init(dda, init, D, N)\
  90.   dda_init_state((dda).state, init, N);\
  91.   dda_init_step((dda).step, D, N)
  92. /*
  93.  * Compute the sum of two DDA steps with the same D and N.
  94.  * Note that since dR + NdR = N, this quantity must be the same in both
  95.  * fromstep and tostep.
  96.  */
  97. #define dda_step_add(tostep, fromstep)\
  98.   (tostep).dQ +=\
  99.     ((tostep).dR < (fromstep).NdR ?\
  100.      ((tostep).dR += (fromstep).dR, (tostep).NdR -= (fromstep).dR,\
  101.       (fromstep).dQ) :\
  102.      ((tostep).dR -= (fromstep).NdR, (tostep).NdR += (fromstep).NdR,\
  103.       (fromstep).dQ + 1))
  104. /*
  105.  * Return the current value in a DDA.
  106.  */
  107. #define dda_state_current(dstate) (dstate).Q
  108. #define dda_current(dda) dda_state_current((dda).state)
  109. #define dda_current_fixed2int(dda)\
  110.   fixed2int_var(dda_state_current((dda).state))
  111. /*
  112.  * Increment a DDA to the next point.
  113.  * Returns the updated current value.
  114.  */
  115. #define dda_state_next(dstate, dstep)\
  116.   (dstate).Q +=\
  117.     ((dstate).R > (dstep).dR ?\
  118.      ((dstate).R -= (dstep).dR, (dstep).dQ) :\
  119.      ((dstate).R += (dstep).NdR, (dstep).dQ + 1))
  120. #define dda_next(dda) dda_state_next((dda).state, (dda).step)
  121. /*
  122.  * Back up a DDA to the previous point.
  123.  * Returns the updated current value.
  124.  */
  125. #define dda_state_previous(dstate, dstep)\
  126.   (dstate).Q -=\
  127.     ((dstate).R <= (dstep).NdR ?\
  128.      ((dstate).R += (dstep).dR, (dstep).dQ) :\
  129.      ((dstate).R -= (dstep).NdR, (dstep).dQ + 1))
  130. #define dda_previous(dda) dda_state_previous((dda).state, (dda).step)
  131. /*
  132.  * Advance a DDA by an arbitrary number of steps.
  133.  * This implementation is very inefficient; we'll improve it if needed.
  134.  */
  135. #define dda_state_advance(dstate, dstep, nsteps)\
  136.   BEGIN\
  137.     uint n_ = (nsteps);\
  138.     (dstate).Q += (dstep).dQ * (nsteps);\
  139.     while ( n_-- )\
  140.       if ( (dstate).R > (dstep).dR ) (dstate).R -= (dstep).dR;\
  141.       else (dstate).R += (dstep).NdR, (dstate).Q++;\
  142.   END
  143. #define dda_advance(dda, nsteps)\
  144.   dda_state_advance((dda).state, (dda).step, nsteps)
  145. /*
  146.  * Translate the position of a DDA by a given amount.
  147.  */
  148. #define dda_state_translate(dstate, delta)\
  149.   ((dstate).Q += (delta))
  150. #define dda_translate(dda, delta)\
  151.   dda_state_translate((dda).state, delta)
  152.  
  153. #endif /* gxdda_INCLUDED */
  154.